Q: What is the use of the bin data structure?
Solution: Bin data structure allows us to have efficient region queries. A frequency of bin is increased by one each time a data point falls into a bin.
Q: What is the worst case time complexity of query operation(n is the no. of candidates)?
Solution: The worst case in a bin query occurs when all the candidates are concentrated in one bin. So in this case the time complexity is O(n).
Q: What is the worst case time complexity of delete operation(n is the no. of candidates)?
Solution: The worst case in a bin delete operation occurs when all the candidates are concentrated in one bin. So in this case the time complexity is O(n).
Q: What is the worst case time complexity of insertion operation(n =no. of candidates)?
Solution: The worst case in a bin insert operation occurs when all the candidates are concentrated in one bin. So in this case the time complexity is O(1).
Q: What is computational geometry?
Solution: Computational geometry deals with the study of algorithms which can be expressed in terms of geometry. Bin data structure is an example of it.
Q: What will be the time complexity of query operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (k = number of bins query rectangle intersects)
Solution: The process of query becomes faster in a case when the number of candidates are equally distributed among the bins. In such a case the query operation becomes O(k).
Q: What will be the time complexity of delete operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (m = number of bins intersecting candidate intersects)
Solution: The process of deletion becomes faster in a case when the number of candidates are equally distributed among the bins. In such a case the query operation becomes O(m). It is practically slower than insertion in this case.
Q: What will be the time complexity of insertion operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (m = number of bins intersecting candidate intersects)
Solution: The process of insertion becomes faster in the case when the number of candidates are equally distributed among the bins. In such a case the query operation becomes O(m). It is practically faster than deletion in this case.
Q: Efficiency of bin depends upon ___________
Solution: Efficiency of bin depends upon the location and size of query and candidates. It is similar to that of a hash table.
Q: Bigger the query rectangle the better is the query efficiency.
Solution: Efficiency of bin depends upon the location and size of query and candidates. Also, the smaller is the query rectangle the better is the query efficiency.
You Have Score    | /10 |